package ACWing.TheNnderlyingAlgorithm.快排;
//785. 快速排序
import java.util.Scanner;

/**
 * @author :chenjie
 * @date :Created 2022/11/16 21:50
 */
public class QuickSort {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[]arr=new int[n];
        for (int i = 0; i < n; i++) {
            arr[i]=sc.nextInt();
        }
        sort(0,n-1,arr);
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i]+" ");
        }
        
    }
    public static void sort(int l,int r,int[]arr){
        if(r<=l){
            return;
        }
        int i=l-1,j=r+1;
        int mid=arr[l+r>>1];
        while (i<j){
            do {
                i++;
            }while (arr[i]<mid);
            do {
                j--;
            }while (arr[j]>mid);
            if(i<j){
                int temp=arr[j];
                arr[j]=arr[i];
                arr[i]=temp;
            }
        }
        sort(l,j,arr);
        sort(j+1,r,arr);
    }

}
